package P810;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Problema da disciplina de Estrutura de Dados e Complexidade de Algoritmos da
 * Pos Graduacao do Periodo 2011.1
 *
 * @see http://br.spoj.pl/problems/REDOTICA/
 * @author Elenilson Vieira - 111100371 - elenilson[at]elenilsonvieira.com
 * @since 18 de junho de 2011
 */
public class Main {

    public static final int MAX_IMPACT_VALUE = 100;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String line = null;
        int testNumber = 1;
        StringBuilder result = new StringBuilder();

        while (!(line = reader.readLine().trim()).equals("0 0")) {
            String data[] = line.split(" ");
            int tabasAmount = Integer.parseInt(data[0]);
            int branchAmount = Integer.parseInt(data[1]);
            StringBuilder branches = new StringBuilder();
            int[][] enviromentalImpact = new int[tabasAmount][tabasAmount];
            boolean[] nodeInMinimumTree = new boolean[tabasAmount];
            int[] distanceToMinimumSpanningTree = new int[tabasAmount];
            int[] indexNodeToBeLinked = new int[tabasAmount];

            for (int i= 0; i < branchAmount; i++) {
                line = reader.readLine();
                data = line.split(" ");
                int tabaX = Integer.parseInt(data[0]);
                int tabaY = Integer.parseInt(data[1]);
                int enviromentalImpactXY = Integer.parseInt(data[2]);

                enviromentalImpact[tabaX - 1][tabaY - 1] = enviromentalImpactXY;
                enviromentalImpact[tabaY - 1][tabaX - 1] = enviromentalImpactXY;
            }

            for (int i = 0; i < tabasAmount; i++)
                distanceToMinimumSpanningTree[i] = MAX_IMPACT_VALUE + 1;

            nodeInMinimumTree[0] = true;
            updateNodeDistances(enviromentalImpact, 0, distanceToMinimumSpanningTree, indexNodeToBeLinked);

            for (int i = 1; i < tabasAmount; i++) {
                int minimum = -1;

                for (int j = 0; j < tabasAmount; j++){
                    if (!nodeInMinimumTree[j])
                        if (minimum == -1 || (distanceToMinimumSpanningTree[minimum] > distanceToMinimumSpanningTree[j]))
                            minimum = j;
                }

                nodeInMinimumTree[minimum] = true;

                int first = -1;
                int last = -1;

                if(indexNodeToBeLinked[minimum] < minimum){
                    first = indexNodeToBeLinked[minimum];
                    last = minimum;
                }else{
                    first = minimum;
                    last = indexNodeToBeLinked[minimum];
                }

                branches.append(first + 1).append(" ").append(last + 1).append("\n");

                updateNodeDistances(enviromentalImpact, minimum, distanceToMinimumSpanningTree, indexNodeToBeLinked);
            }

            result.append(testNumber == 1 ?
                    String.format("Teste %d\n%s\n", testNumber++, branches.toString().trim()) :
                    String.format("\nTeste %d\n%s\n", testNumber++, branches.toString().trim()));
        }

        System.out.print(result.toString());
    }

    /**
     * Atualiza a distancia de um no
     *
     * @param enviromentalImpact o array com os impactos das ligacoes
     * @param node o no
     * @param distanceToMinimumSpanningTree as distancias dos nos pra arvore de minimo impacto
     * @param indexNodeToBeLinked o array de posicoes que diz quem o no atual esta referenciando para o calculo do menor impacto
     */
    private static void updateNodeDistances(int[][] enviromentalImpact, int node, int[] distanceToMinimumSpanningTree, int[] indexNodeToBeLinked) {
        for (int i = 0; i < enviromentalImpact.length; i++)
            if ((enviromentalImpact[node][i] != 0) && (distanceToMinimumSpanningTree[i] > enviromentalImpact[node][i])) {
                distanceToMinimumSpanningTree[i] = enviromentalImpact[node][i];
                indexNodeToBeLinked[i] = node;
        }
    }
}
